from random import sample
from Graph import *
from copy import deepcopy
class AllMatchMC:

    slots = ["graph", "matching"]

    def __init__(self, graph):
        self.graph = graph
        self.matching = []
    #this is the function that transitions the matching
    def takeStep(self):
        #randomly select our edge
        e = sample(self.graph.edges,1)[0] 
        m = deepcopy(self.matching)
        
        #compute a list of vertices that are covered already
        verticesCovered = []
        for x in m:
            if verticesCovered.count(x[0]) == 0:
                verticesCovered.append(x[0])
            if verticesCovered.count(x[1]) == 0:
                verticesCovered.append(x[1])
        #find out which of our edges vertices are already covered
        e0covered = verticesCovered.count(e[0]) == 1
        e1covered = verticesCovered.count(e[1]) == 1

        #if the edge is already there, drop it
        if m.count(e) > 0:
            m.remove(e)

        #otherwise, add it    
        elif not (e0covered or e1covered):
            m.append(e)

        #finally, if one of our vertices is covered, find the edge, drop it
        #and add the new one
        elif e0covered ^ e1covered: 
            dropEdge = None
            if e0covered:
                for x in m:
                    if x.count(e[0]) > 0:
                        dropEdge = x
            elif e1covered:
                for x in m:
                    if x.count(e[1]) > 0:
                        dropEdge = x
            m.remove(dropEdge)
            m.append(e)
        self.matching = m

g = kgraphgen(10)
print(g)
mc = AllMatchMC(g)
for i in range(50):
    mc.takeStep()
    print(mc.matching)
